package com.myc.subjects.binarysearch;

/**
 * 二分查找练习
 * 时间复杂度：O(log^n)
 * 并非LeetCode题目
 * 仅仅是练习手写二分查找
 */
public class Erfenchazhao {

    /**
     * 循环方式
     */
    public static int binarySearch1(int[] array,int key){
        //定义左右指针
        int low = 0;
        int high = array.length - 1;

        //判断边界情况
        if(key < array[low] || key > array[high])
            return -1;

        //一般情况
        while(low <= high){//逐一退出循环条件是左指针大于右指针
            int mid = (high + low) / 2;//中间指针
            if(key > array[mid]){
                low = mid + 1;
            }else if(key < array[mid]){
                high = mid - 1;
            }else{
                return mid;
            }
        }

        //没找到则不存在
        return -1;
    }

    /**
     * 递归方式
     */
    public static int binarySearch2(int[] array,int key, int fromIndex, int toIndex){//需要层层传递的变化的数据放在参数里，这里需要传递的是收尾指针
        //判断边界情况(递归出口)
        if(key < array[fromIndex] || key > array[toIndex] || fromIndex > toIndex){
            return -1;
        }

        //定义中间指针
        int mid = (fromIndex + toIndex) / 2;

        //处理一般情况，改变收尾指针，递归调用
        if(key > array[mid])
            return binarySearch2(array, key, mid + 1, toIndex);
        else if(key < array[mid])
            return binarySearch2(array, key, fromIndex, mid - 1);
        else
            return mid;
    }

    public static void main(String[] args) {

        int[] array = {1,3,5,8,9,12,24,58,59,79};

        int key = 58;

        System.out.println(Erfenchazhao.binarySearch2(array, key, 0, array.length - 1));

    }
}

/**
 * 总结：
 *
 * 循环方式：
 * 1.使用二分查找的必要条件是要先排序
 * 2.和其他左右指针问题一样：
 *    定义左右指针 -> 判断边界情况 -> 处理一般情况 while(边界条件)
 *
 * 递归方式：
 * 1.需要层层传递的变化的数据放在参数里
 * 2.判断边界情况，同时也是递归的出口
 * 3.处理一般情况，递归调用
 *
 *
 * 循环方式的优势：空间复杂度是常数级，而递归方式空间复杂度也是O{log^n}
 * 递归方式的优势：代码更加精简
 */
